#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s;
        p = ' ' + p;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int i = 2;i <= n;i += 2)
        {
            if (p[i] == '*') dp[0][i] = true;
            else break;
        }

        for (int i = 1;i <= m;i++)
        {
            for (int j = 1;j <= n;j++)
            {
                if (p[j] >= 'a' && p[j] <= 'z')
                {
                    if (s[i] == p[j]) dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p[j] == '.') dp[i][j] = dp[i - 1][j - 1];
                else if (p[j] == '*')
                {
                    if (p[j - 1] == '.')
                    {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }
                    else
                    {
                        dp[i][j] = dp[i][j - 2] || (s[i] == p[j - 1] && dp[i - 1][j]);
                    }
                }

            }
        }
        return dp[m][n];
    }
};